Rakiety

Limit pamięci: 32 MB

Na płaskiej mapie wyznaczono dwa rozłączne, -elementowe zbiory punktów: i . Żadne trzy punkty ze zbioru nie są współliniowe. W punktach ze zbioru rozlokowane są rakiety typu ziemia-ziemia, natomiast w punktach ze zbioru znajdują się obiekty wroga, które trzeba zniszczyć. Rakiety mogą lecieć jedynie w linii prostej, a tory rakiet nie mogą się przecinać. Chcemy dla każdej rakiety wyznaczyć cel, który powinna zniszczyć.

Zadanie

Napisz program, który:

• wczytuje ze standardowego wejścia współrzędne punktów ze zbiorów i ,
• wyznacza zbiór parami nie przecinających się odcinków i takich, że jeden koniec każdego odcinka należy do zbioru , podczas gdy drugi należy do zbioru ,
• wypisuje wynik na standardowe wyjście.

Wejście

W pierwszym wierszu standardowego wejścia jest zapisana jedna liczba naturalna , , równa liczności zbiorów i .

W każdym z kolejnych wierszy wejścia jest zapisana para liczb całkowitych z przedziału oddzielonych pojedynczym odstępem. Są to współrzędne punktu na płaszczyźnie (najpierw współrzędna , potem współrzędna ). Pierwsze z tych wierszy zawiera współrzędne punktów ze zbioru , natomiast ostatnie wierszy zawiera współrzędne punktów ze zbioru . W wierszu o numerze znajdują się współrzędne punktu , natomiast w wierszu o numerze znajdują się współrzędne punktu , .

Wyjście

Standardowe wyjście powinno składać się z wierszy. W -tym wierszu należy zapisać jedną liczbę naturalną taką, że odcinek należy do wyznaczonego zbioru odcinków (innymi słowy, że rakieta z punktu ma zniszczyć obiekt położony w punkcie ).

Przykład

Dla danych wejściowych:

4
0 0
1 5
4 2
2 6
1 2
5 4
4 5
3 1

poprawną odpowiedzią jest:

2
1
4
3

Autor zadania: Wojciech Rytter.